package algorithmic_data_structure.快排;

import org.junit.Test;

public class 快速排序_有重复元素 {
    public void quickSort(int[] nums){
        if (nums == null || nums.length == 0){
            return ;
        }
        quickSortAndPartition(nums,0,nums.length-1);
    }

    private void quickSortAndPartition(int[] nums, int left, int right) {
        if (left >= right){
            return ;
        }
        int[] equalArea = Partition(nums,left,right);//取出重复元素的范围
        quickSortAndPartition(nums,left,equalArea[0]-1);
        quickSortAndPartition(nums,equalArea[1]+1,right);
    }

    private int[] Partition(int[] nums, int left, int right) {
        if (left > right){//这里有点累赘，保险起见
            return new int[]{-1,-1};
        }
        if (left == right){
            return new int[]{1,1};
        }
        swap(nums,left+ (int)(Math.random()*(right-left+1)),right);//避免出现最坏情况
        int leftSide = left-1;//左边界
        int rightSide = right;//右边界，同时使用最右的元素作为基准
        int index = left;//唯一指针，这里使用的不是双指针，而是单指针，
        int P = nums[right];//基准
        // 如果当前元素是小于基准的，就与右边界前的元素交换，并且左边界与指针同时右移
        // 如果当前元素是大于基准的，就与右边界前的元素交换，并且指针不动，右边界左移
        // 可以想象成如果是小于基准的就被左边界吃掉，大于基准的就被右边界吃掉
        while (index < rightSide){
            if (nums[index] == P){
                //当前元素等于基准的情况就是指针右移，左边界不动，左边界吃不了相等的数
                index++;
            }else if (nums[index] > P){
                //当前元素大于基准,与右边界前一个元素交换,右边界左移，指针不动,是因为这个从右部换过来的数还没判断过
                swap(nums,index,--rightSide);
            }else{
                //当前元素小于基准,与左边界前一个元素交换，指针 与 左边界 同时右移
                swap(nums,index++,++leftSide);
            }
        }
        //推出是的状态是 index == rightSide，也就是说还有一个元素没有处理，右边界前一个数，是比基准要大的（为什么？）
        swap(nums,right,rightSide);
        return new int[]{leftSide+1,rightSide};
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
    @Test
    public void test(){
        int[] array = new int[]{9,8,7,7,5,4,6,5,3,2,1,5,4,3};
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println("排序后：");
        quickSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
}
